COMBINATIONS

Tags: #◇Computer Science #◇STT101A #◇Conceptual #◇Combinations

---

◇Overview

A Combination is a selection of $r$ objects from a set of $n$ distinct objects without regard to order (and without replacement). While permutations treat $(A, B)$ and $(B, A)$ as distinct arrangements, combinations treat $\{A, B\}$ as a single subset.

◇Key Definitions

• Binomial Coefficient ($\binom{n}{r}$ or $_nC_r$): The number of $r$-element subsets chosen from $n$ distinct elements:
  $\binom{n}{r} = \frac{P(n, r)}{r!} = \frac{n!}{r!(n - r)!}, \quad 0 \le r \le n$
• Symmetry Identity: $\binom{n}{r} = \binom{n}{n - r}$ (choosing $r$ items to include is equivalent to choosing $n - r$ items to leave behind).
• Pascal's Identity: $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$.
• Total Subsets Identity: $\sum_{r=0}^n \binom{n}{r} = 2^n$.

◇Worked Example

Problem: From a pool of $8$ cybersecurity engineers and $6$ network administrators, how many ways can a $5$-person incident response committee be formed if it must contain exactly $3$ cybersecurity engineers and $2$ network administrators?

Solution:
$\binom{8}{3} \times \binom{6}{2} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} \times \frac{6 \times 5}{2 \times 1} = 56 \times 15 = 840$

◇References & Navigation

• Previous Topic: ◇Permutations
• Next Topic: ◇Basic Formula of Probability
• Related Notes: ◇Counting by Cases, ◇Expected Event